package Demo4;

import java.util.Stack;

/**
 * @ClassName SymmetryCheckWithStack
 * @Description 用栈检查字符串的对称性
 * @Author ZJX
 * @Date 2024/9/18 11:29
 * @Version 1.0
 */
public class SymmetryCheckWithStack {
    // 链表节点定义
    static class Node {
        char data;
        Node next;

        public Node(char data) {
            this.data = data;
        }
    }

    public boolean isSymmetric(Node head) {
        if (head == null || head.next == null) {
            return true;  // 空链表或只有一个字符时，认为是对称的
        }

        Stack<Character> stack = new Stack<>();
        
        Node fast = head;
        Node slow = head;
       while(fast != null && fast.next != null){
           stack.push(slow.data);
           fast = fast.next.next;
           slow = slow.next;
       }


        // 如果链表长度是奇数，跳过中间的节点
        if (fast != null) {
            slow = slow.next;  // 跳过中间节点，因为它不需要参与对称比较
        }

        while(slow != null){
            if (stack.pop() != slow.data){
                return false;
            }
            slow = slow.next;
        }
        return true;
    }

    // 构造链表
    public Node createList(char[] values) {
        if (values.length == 0) return null;

        Node head = new Node(values[0]);
        Node cur = head;

        for (int i = 1; i < values.length; i++) {
            cur.next = new Node(values[i]);
            cur = cur.next;
        }
        return head;
    }

    public static void main(String[] args) {
        SymmetryCheckWithStack test = new SymmetryCheckWithStack();
        char[] values = {'x','y','z','y','x'};
        Node testList = test.createList(values);
        System.out.println(test.isSymmetric(testList));
    }

}
